package org.jheaps.array

import org.jheaps.Heap
import org.jheaps.annotations.ConstantTime
import java.io.Serializable
import kotlin.math.max

/**
 * An abstract weak heap with an array representation.
 *
 * @author Dimitrios Michail
 *
 * @param <K>
 * the type of keys maintained by this heap
</K> */
abstract class AbstractArrayWeakHeap<K>(comparator: Comparator<in K?>?, capacity: Int) : Heap<K>, Serializable {
    /**
     * The comparator used to maintain order in this heap, or null if it uses
     * the natural ordering of its keys.
     *
     * @serial
     */
    protected val comparator: Comparator<in K?>?

    /**
     * The array used for representing the heap.
     */
    protected lateinit var array: Array<K?>

    /**
     * Number of elements in the heap.
     */
    protected var size: Int

    /**
     * Minimum capacity due to initially requested capacity.
     */
    protected val minCapacity: Int

    /**
     * Constructor
     *
     * @param comparator
     * the comparator to use
     * @param capacity
     * the requested capacity
     */
    init {
        checkCapacity(capacity)
        this.size = 0
        this.comparator = comparator
        this.minCapacity = max(capacity.toDouble(), DOWNSIZING_MIN_HEAP_CAPACITY.toDouble()).toInt()
        initCapacity(minCapacity)
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        /**
         * {@inheritDoc}
         */
        get() {
            return size == 0
        }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size.toLong()
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun clear() {
        size = 0
    }

    /**
     * Check that a capacity is valid.
     *
     * @param capacity
     * the capacity
     *
     * @throws IllegalArgumentException
     * if the capacity is negative or more than the maximum array
     * size
     */
    protected fun checkCapacity(capacity: Int) {
        if (capacity < MIN_HEAP_CAPACITY) {
            throw IllegalArgumentException("Heap capacity must be >= " + MIN_HEAP_CAPACITY)
        }
        if (capacity > MAX_HEAP_CAPACITY) {
            throw IllegalArgumentException("Heap capacity too large")
        }
    }

    /**
     * Initialize array representation.
     *
     * @param capacity
     * the capacity
     */
    protected abstract fun initCapacity(capacity: Int)

    /**
     * Make sure the array representation can hold a certain number of elements.
     *
     * @param capacity
     * the capacity
     */
    protected abstract fun ensureCapacity(capacity: Int)

    /**
     * Upwards fix starting from a particular element
     *
     * @param k
     * the index of the starting element
     */
    protected abstract fun fixup(k: Int)

    /**
     * Upwards fix starting from a particular element. Performs comparisons
     * using the comparator.
     *
     * @param k
     * the index of the starting element
     */
    protected abstract fun fixupWithComparator(k: Int)

    /**
     * Downwards fix starting from a particular element
     *
     * @param k
     * the index of the starting element
     */
    protected abstract fun fixdown(k: Int)

    /**
     * Downwards fix starting from a particular element. Performs comparisons
     * using the comparator.
     *
     * @param k
     * the index of the starting element
     */
    protected abstract fun fixdownWithComparator(k: Int)

    companion object {
        private val serialVersionUID: Long = 1L

        /**
         * The maximum heap capacity.
         */
        protected val MAX_HEAP_CAPACITY: Int = Int.MAX_VALUE - 8 - 1

        /**
         * The minimum heap capacity.
         */
        protected val MIN_HEAP_CAPACITY: Int = 0

        /**
         * Limit for the heap capacity when down-sizing.
         */
        protected val DOWNSIZING_MIN_HEAP_CAPACITY: Int = 16
    }
}
